package _01_链表;

/**
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list/
 * @author : zjj
 * @date : 2021/1/13 15:24
 */
public class _206_反转链表 {
    /**
     * 思路：
     * 新节点指向原来的头节点，找一个临时的变量指向头节点的下一个节点
     * @param head  头节点
     * @return      反转后的头节点
     */
    public ListNode reverseList(ListNode head) {
        // 特殊情况的考虑  ，只有一个节点 和 没有节点
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = null ;
        while (head != null){
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    /**
     * 递归调用
     * @param head  头节点
     * @return      反转后的头节点
     */
    public ListNode reverseList2(ListNode head){
        if (head ==null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList2(head.next);
        head.next.next = head ;
        head.next = null ;
        return newHead;
    }


}
